#include <stdio.h>
#include <stdlib.h>

typedef char Item;
typedef struct node *link;

struct node {
    Item item;
    link l;
    link r;
};

link NEW(Item item, link l, link r);
link max(Item a[], int l, int r);
void printnode(char c, int h);
void show(link x, int h);

int main(int argc, char **argv){
    Item a[] = {'A', 'M', 'P', 'L', 'E'};
    link root = max(a, 0, 4);
    show(root, 2);
    return 0;
}

link NEW(Item item, link l, link r){
    link x = malloc(sizeof(*x));
    x->item = item;
    x->l = l;
    x->r = r;
    return x;
}


link max(Item a[], int l, int r){
    int m = (l+r)/2;
    link x = NEW(a[m], NULL, NULL);
    if (l == r) {
        return x;
    }
    x->l = max(a, l, m);
    x->r = max(a, m+1, r);
    Item u = x->l->item;
    Item v = x->r->item;
    if (u > v) {
        x->item = u;
    }else {
        x->item = v;
    }
    return x;
}

void show(link x, int h){
    if (x == NULL) {
        printnode('*', h);
        return ;
    }
    show(x->r, h+1);
    printnode(x->item, h);
    show(x->l, h+1);
}

void printnode(char c, int h){
    int i;

    for (i = 0; i < h; i++) {
        printf("  ");
    }
    printf("%c\n", c);
}

